package pri.zjy.dynamicProgramming;

/**
 * @author zhangjy
 * @description 最长连续递增序列
 * @date 2025/5/29 11:21
 */
public class FindLengthOfLCIS_674 {

    public static void main(String[] args) {

    }

    /**
     * dmsxl：贪心
     * <p>
     * 思路：遇到nums[i] > nums[i - 1]的情况，count就++，否则count为1，记录count的最大值就可以
     */
    public int findLengthOfLCIS4(int[] nums) {
        if (nums.length == 0) return 0;
        int res = 1; // 连续子序列最少也是1
        int count = 1;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i + 1] > nums[i]) { // 连续记录
                count++;
            } else { // 不连续，count从头开始
                count = 1;
            }
            if (count > res) res = count;
        }
        return res;
    }

    /**
     * 官解：贪心
     * <p>
     * 分析：
     * 记录当前连续递增序列的开始下标和结束下标，遍历数组的过程中每次比较相邻元素，根据相邻元素的大小关系决定是否需要更新连续递增序列的开始下标。
     * 若遇到nums[i] <= nums[i - 1]的情况，就需要重置 最长连续严格递增子序列的起始下标start；否则，记录满足条件子序列的最大长度
     * <p>
     * T(n) = O(n)；其中，n是nums数组每一个元素，都要处理一次。
     * S(n) = O(1)
     */
    public int findLengthOfLCIS3(int[] nums) {
        int ans = 0;
        int n = nums.length;
        int start = 0;
        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] <= nums[i - 1]) {
                start = i;
            }
            ans = Math.max(ans, i - start + 1);
        }
        return ans;
    }

    /**
     * 个解：dp-参照dmsxl
     * <p>
     * T(n) = O(n)；其中，n是nums数组每一个元素，都要处理一次。
     * S(n) = O(n)；dp数组花费的空间。
     */
    public int findLengthOfLCIS2(int[] nums) {
        if (nums.length == 0) return 0;

        // 1.dp[i]
        //  以 i 为结尾的，最长 连续 严格递增 子序列的长度
        int[] dp = new int[nums.length];

        // 2.递推公式
        // 若nums[i]>nums[i-1]，则dp[i]=dp[i-1]+1。因为要求连续，所以只用和前一位相比。

        // 3.初始化
        // dp[1]可由dp[0]推导
        dp[0] = 1;

        // 4.遍历
        // dp[i]与前一项有关，所以从前往后
        int maxLength = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            if (nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;

            // 记录满足条件的最大长度
            maxLength = Math.max(maxLength, dp[i]);
        }

        return maxLength;
    }

    /**
     * dmsxl：dp
     * <p>
     * 注意：连续最长递增
     */
    public int findLengthOfLCIS(int[] nums) {
        // 1.dp[i]，表示以下标 i 结尾的最长连续递增子序列的长度
        int[] dp = new int[nums.length];

        // 2.递推公式
        // 若nums[i]>nums[i-1]，则dp[i]=dp[i-1]+1；否则dp[i]=1

        // 3.初始化
        // dp[1]可以由dp[0]推导出来，所以不用初始化
        dp[0] = 1;

        // 4.遍历顺序
        // dp[i]依赖前一项，所以从前往后
        int maxLength = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            if (nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;

            maxLength = Math.max(maxLength, dp[i]);
        }
        return maxLength;
    }

}
